
#include <iostream>
#include <fstream>
#include "lklist.h"

using namespace std;

typedef int elemtype;
typedef lklisttpl<elemtype> lklist;

lklist *merge( lklist *, lklist * );

int main()
{
    ifstream in("in.txt");
    vector<elemtype> va, vb;
    lklist *ha, *hb, *hc;
    int i, n;
    int t;

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	va.push_back(t);
    }

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	vb.push_back(t);
    }

    ha = createlk<lklist,elemtype>( va, WITHHEAD );
    printlk( ha, WITHHEAD ); cout << endl;

    hb = createlk<lklist,elemtype>( vb, WITHHEAD );
    printlk( hb, WITHHEAD ); cout << endl;

    hc = merge( ha, hb );
    printlk( hc, WITHHEAD ); cout << endl;

    destorylk( ha, WITHHEAD );
    destorylk( hb, WITHHEAD );
    destorylk( hc, WITHHEAD );

    return 0;
}

/* ******************************************************
 *             Answer to this question.
 * ******************************************************/

lklist *merge( lklist *a, lklist *b )
{
    lklist *c, *pa, *pb, *pc;
    
    c = new lklist;
    c->next = NULL;
    pc = c;
    while( a->next && b->next ){
        
        pa = a->next;
        a->next = pa->next;
        pa->next = pc->next;
        pc->next = pa;
        pc = pc->next;
        
        pb = b->next;
        b->next = pb->next;
        pb->next = pc->next;
        pc->next = pb;
        pc = pc->next;
        
    }
    
    if( a->next ){
	pc->next = a->next;
	a->next = NULL;
    }
    else{
	pc->next = b->next;
	b->next = NULL;
    }
    
    return c;
}
